<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <p data-lake-id="u0ac03769" id="u0ac03769"><span data-lake-id="u6de09b5a" id="u6de09b5a">缓存失效算法主要是进行缓存失效的，当缓存中的存储的对象过多时，需要通过一定的算法选择出需要被淘汰的对象，一个好的算法对缓存的命中率影响是巨大的。常见的缓存失效算法有FIFO、LRU、LFU，以及Caffeine中的Window </span><span data-lake-id="uadc33609" id="uadc33609" style="color: rgb(49, 70, 89)">TinyLFU算法。</span></p>
  <p data-lake-id="u6586ad4e" id="u6586ad4e"><span data-lake-id="u4afc01d0" id="u4afc01d0" style="color: rgb(49, 70, 89)">​</span><br></p>
  <h3 data-lake-id="gMdsI" id="gMdsI"><span data-lake-id="u1ece434c" id="u1ece434c" style="color: rgb(49, 70, 89)">FIFO</span></h3>
  <p data-lake-id="u8a2b9f6b" id="u8a2b9f6b"><br></p>
  <p data-lake-id="u1c0b9657" id="u1c0b9657"><span data-lake-id="u894ec1ba" id="u894ec1ba">FIFO 算法是一种比较容易实现也最容易理解的算法。它的主要思想就是和队列是一样的，即先进先出（First In First Out）</span></p>
  <p data-lake-id="u5b657a7b" id="u5b657a7b"><span data-lake-id="u4805eb18" id="u4805eb18">​</span><br></p>
  <p data-lake-id="ud877fdb5" id="ud877fdb5"><span data-lake-id="ub8492039" id="ub8492039">一般认为一个数据是最先进入的，那么可以认为在将来它被访问的可能性很小。</span></p>
  <p data-lake-id="u3a6f31c8" id="u3a6f31c8"><span data-lake-id="ub3e61b5f" id="ub3e61b5f">​</span><br></p>
  <p data-lake-id="u8db46eda" id="u8db46eda"><span data-lake-id="u0a7a7886" id="u0a7a7886">因为FIFO刚好符合队列的特性，所以通常FIFO的算法都是使用队列来实现的：</span></p>
  <p data-lake-id="u31fe8de0" id="u31fe8de0"><span data-lake-id="u42800daa" id="u42800daa">​</span><br></p>
  <p data-lake-id="ud2f1ce50" id="ud2f1ce50"><img src="https://cdn.nlark.com/yuque/0/2022/png/5378072/1672296682476-98ee6a2f-871c-4d2d-bc95-b8b70e8d9f43.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_38%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ud468ea14" id="ud468ea14"><span data-lake-id="u79182225" id="u79182225" class="lake-fontsize-14" style="color: rgb(54, 46, 43)">​</span><br></p>
  <p data-lake-id="u77bbf8ae" id="u77bbf8ae"><span data-lake-id="ud5c4f8d6" id="ud5c4f8d6">1. 新数据插入到队列尾部，数据在队列中顺序移动；</span></p>
  <p data-lake-id="u76c8cdb1" id="u76c8cdb1"><span data-lake-id="u8aa20a18" id="u8aa20a18">2. 淘汰队列头部的数据；</span></p>
  <p data-lake-id="u7e4a9984" id="u7e4a9984"><br></p>
  <h3 data-lake-id="yuvKi" id="yuvKi"><span data-lake-id="u4335a4a4" id="u4335a4a4">LRU</span></h3>
  <p data-lake-id="u2333b9c2" id="u2333b9c2"><br></p>
  <p data-lake-id="ucde15c32" id="ucde15c32"><span data-lake-id="u5634e6fb" id="u5634e6fb">LRU（The Least Recently Used，最近最少使用）是一种常见的缓存算法，在很多分布式缓存系统（如Redis, Memcached）中都有广泛使用。</span></p>
  <p data-lake-id="u6e123e12" id="u6e123e12"><span data-lake-id="ucecb1a86" id="ucecb1a86">​</span><br></p>
  <p data-lake-id="u7fbfa038" id="u7fbfa038"><span data-lake-id="u1daa8f06" id="u1daa8f06">LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被淘汰。</span></p>
  <p data-lake-id="ubdbb6377" id="ubdbb6377"><span data-lake-id="u77a022e8" id="u77a022e8">​</span><br></p>
  <p data-lake-id="u31b8dd8e" id="u31b8dd8e"><span data-lake-id="u1581cf0c" id="u1581cf0c">最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：</span></p>
  <p data-lake-id="ud8ec390a" id="ud8ec390a"><span data-lake-id="ud41abe55" id="ud41abe55">​</span><br></p>
  <p data-lake-id="ud7b4f958" id="ud7b4f958"><img src="https://cdn.nlark.com/yuque/0/2022/png/5378072/1672297308812-4613871f-5f49-45f9-92b6-057d948bc076.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_48%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ub01d489e" id="ub01d489e"><br></p>
  <p data-lake-id="u24bb50b9" id="u24bb50b9"><span data-lake-id="uce52f762" id="uce52f762">1. 新数据插入到链表头部；</span></p>
  <p data-lake-id="u10dcfe43" id="u10dcfe43"><span data-lake-id="u62296f12" id="u62296f12">2. 每当缓存命中，则将数据移到链表头部；</span></p>
  <p data-lake-id="u36c763ef" id="u36c763ef"><span data-lake-id="u9793b704" id="u9793b704">3. 当链表满的时候，将链表尾部的数据丢弃。</span></p>
  <p data-lake-id="u8333812e" id="u8333812e"><br></p>
  <h3 data-lake-id="XNeWW" id="XNeWW"><span data-lake-id="uf5cd0d76" id="uf5cd0d76">LFU</span></h3>
  <p data-lake-id="uc59dd1c2" id="uc59dd1c2"><span data-lake-id="u281dc440" id="u281dc440">LFU（Least Frequently Used ，最近最不常用）也是一种常见的缓存算法。</span></p>
  <p data-lake-id="u1e9c2c50" id="u1e9c2c50"><span data-lake-id="ucb9ee49e" id="ucb9ee49e">​</span><br></p>
  <p data-lake-id="ubbee1dcb" id="ubbee1dcb"><span data-lake-id="ub7fd882a" id="ub7fd882a">顾名思义，LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。</span></p>
  <p data-lake-id="ub1f35497" id="ub1f35497"><span data-lake-id="ucb2db198" id="ucb2db198">​</span><br></p>
  <p data-lake-id="u0ae4d874" id="u0ae4d874"><span data-lake-id="u9bba69c7" id="u9bba69c7">LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。</span></p>
  <p data-lake-id="ue9205aec" id="ue9205aec"><span data-lake-id="ub97e243a" id="ub97e243a">​</span><br></p>
  <p data-lake-id="u243eefce" id="u243eefce"><span data-lake-id="u2a0526ff" id="u2a0526ff">具体实现如下：</span></p>
  <p data-lake-id="uc89356fc" id="uc89356fc"><span data-lake-id="ue1e26163" id="ue1e26163">​</span><br></p>
  <p data-lake-id="u9f7b56f4" id="u9f7b56f4"><img src="https://cdn.nlark.com/yuque/0/2022/png/5378072/1672297971423-6c8a07d7-d86f-484b-bcd0-2db14d5e83ac.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_51%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u41e94d36" id="u41e94d36"><span data-lake-id="u315ae628" id="u315ae628">​</span><br></p>
  <p data-lake-id="u13877d58" id="u13877d58"><span data-lake-id="u4b7ee6ab" id="u4b7ee6ab">1. 新加入数据插入到队列尾部（因为引用计数为1）；</span></p>
  <p data-lake-id="ua16f5f4d" id="ua16f5f4d"><span data-lake-id="u04653148" id="u04653148">2. 队列中的数据被访问后，引用计数增加，队列重新排序；</span></p>
  <p data-lake-id="uff975712" id="uff975712"><span data-lake-id="u55e288da" id="u55e288da">3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除。</span></p>
  <p data-lake-id="u2664f5de" id="u2664f5de"><br></p>
  <h3 data-lake-id="ZPjZ5" id="ZPjZ5"><span data-lake-id="u998a576b" id="u998a576b">W-TinyLFU</span></h3>
  <p data-lake-id="uc572c400" id="uc572c400"><br></p>
  <p data-lake-id="uefd74e88" id="uefd74e88"><span data-lake-id="uba252763" id="uba252763">LFU 通常能带来最佳的缓存命中率，但 LFU 有两个缺点：</span></p>
  <ol list="uf4b1cbe3">
   <li fid="u0f835c30" data-lake-id="u32a50793" id="u32a50793"><span data-lake-id="u2e10d309" id="u2e10d309">它需要给每个记录项维护频率信息，每次访问都需要更新，需要一个巨大的空间记录所有出现过的 key 和其对应的频次；</span></li>
   <li fid="u0f835c30" data-lake-id="u6ea97846" id="u6ea97846"><span data-lake-id="u72067396" id="u72067396">如果数据访问模式随时间有变，LFU 的频率信息无法随之变化，因此早先频繁访问的记录可能会占据缓存，而后期访问较多的记录则无法被命中；</span></li>
   <li fid="u0f835c30" data-lake-id="u46803dc2" id="u46803dc2"><span data-lake-id="u3eadc408" id="u3eadc408">如果一个刚加入缓存的元素，它的频率并不高，那么它可能会会直接被淘汰。</span></li>
  </ol>
  <p data-lake-id="ue414cd31" id="ue414cd31"><br></p>
  <p data-lake-id="u9d80cf74" id="u9d80cf74"><span data-lake-id="u29c41b6c" id="u29c41b6c">其中第一点过于致命导致我们通常不会使用 LFU。我们最常用的 LRU 实现简单，内存占用低，但其并不能反馈访问频率。LFU 通常需要较大的空间才能保证较好的缓存命中率。</span></p>
  <p data-lake-id="u5fd14087" id="u5fd14087"><br></p>
  <p data-lake-id="ub441d410" id="ub441d410"><span data-lake-id="u934a40dd" id="u934a40dd">W-TinyLFU是一种高效的缓存淘汰算法，它是TinyLFU算法的一种改进版本，主要用于处理大规模缓存系统中的淘汰问题。W-TinyLFU的核心思想是基于窗口的近似最少使用算法，即根据数据的访问模式动态地调整缓存中数据的淘汰策略。</span><strong><span data-lake-id="u73d699b6" id="u73d699b6" style="color: rgb(18, 18, 18)">W-TinyLFU 综合了LRU和LFU的长处：高命中率、低内存占用。</span></strong></p>
  <p data-lake-id="uc654c5e0" id="uc654c5e0"><br></p>
  <p data-lake-id="u7b57f2c7" id="u7b57f2c7"><span data-lake-id="u12039d7f" id="u12039d7f">W-TinyLFU由多个部分组合而成，包括</span><span data-lake-id="u6ebe52e6" id="u6ebe52e6">窗口缓存</span><span data-lake-id="uca798be4" id="uca798be4">、</span><span data-lake-id="uaa01d068" id="uaa01d068">过滤器</span><span data-lake-id="u69b07a02" id="u69b07a02">和</span><span data-lake-id="u018208b7" id="u018208b7">主缓存</span><span data-lake-id="uc7cdf1e2" id="uc7cdf1e2">。</span></p>
  <p data-lake-id="u55e1580f" id="u55e1580f"><span data-lake-id="u7986a3e2" id="u7986a3e2">​</span><br></p>
  <p data-lake-id="uc7b3b97c" id="uc7b3b97c"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1678521862530-0a19129d-32e9-49bd-b491-01a69ee7ec0c.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_59%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ub1a51584" id="ub1a51584"><span data-lake-id="ud83db9f5" id="ud83db9f5">使用LRU来作为一个窗口缓存，主要是让元素能够有机会在窗口缓存中去积累它的频率，避免因为频率很低而直接被淘汰。</span></p>
  <p data-lake-id="u167cc5e1" id="u167cc5e1"><span data-lake-id="u68d77fb2" id="u68d77fb2">​</span><br></p>
  <p data-lake-id="uc24f4966" id="uc24f4966"><span data-lake-id="u6e8af1d0" id="u6e8af1d0">主缓存是使用SLRU，元素刚进入W-TinyLFU会在窗口缓存暂留一会，被挤出窗口缓存时，会在过滤器中和主缓存中最容易被淘汰的元素进行PK，如果频率大于主缓存中这个最容易被淘汰的元素，才能进入主缓存。</span></p>
  <p data-lake-id="ue5b2c793" id="ue5b2c793"><br></p>
  <p data-lake-id="ua50cd735" id="ua50cd735"><span data-lake-id="u387dc1df" id="u387dc1df">​</span><br></p>
  <p data-lake-id="ubf6c3ad5" id="ubf6c3ad5"><span data-lake-id="ueed305d6" id="ueed305d6">​</span><br></p>
  <p data-lake-id="u0667f45c" id="u0667f45c"><span data-lake-id="ud801be56" id="ud801be56">​</span><br></p>
  <p data-lake-id="uaf8ad119" id="uaf8ad119"><span data-lake-id="udd6a8b7a" id="udd6a8b7a">​</span><br></p>
  <p data-lake-id="u37f26daf" id="u37f26daf"><span data-lake-id="u33fa2507" id="u33fa2507">​</span><br></p>
  <p data-lake-id="u456eb966" id="u456eb966"><br></p>
  <p data-lake-id="u63705a3d" id="u63705a3d"><br></p>
  <p data-lake-id="ua32e592d" id="ua32e592d"><span data-lake-id="u6324e30c" id="u6324e30c">​</span><br></p>
  <p data-lake-id="u1ad0bb56" id="u1ad0bb56"><span data-lake-id="ua2d04e4b" id="ua2d04e4b"><br><br></span></p>
  <p data-lake-id="u0794a112" id="u0794a112"><br></p>
 </body>
</html>